package Hot100;

import java.util.PriorityQueue;

/**
 * @author zhangmin
 * @create 2022-01-02 16:41
 */
public class findKthLargest215 {

    /**
     * 215. 数组中的第K个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * 1、排序后取k
     * 2、快速选择
     * 3、二叉堆-小顶堆
     * */
    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int num:nums) {
            queue.offer(num);
            if (queue.size()>k){
                //当堆大小超过 k 的时候，我们就删掉堆顶的元素，因为这些元素比较小，而我们想要的是前 k 个最大元素嘛。
                queue.poll();
            }
        }
        return queue.peek();
    }

    int partition(int[] nums,int left,int right){
        if (left==right) return left;
        int pivot=nums[left];
        int i=left,j=right+1;
        while (true){
            while (nums[++i]<pivot){
                if (i==right) break;
            }
            while (nums[--j]>pivot){
                if (j==left) break;
            }
            if (i>=j) break;
            swap(nums,i,j);
        }
        swap(nums,left,j);
        return j;
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        k=nums.length-k;
        while (left<=right){
            int partition = partition(nums, left, right);
            if (partition<k){
                //划分点左边的数量小于k，需要在右边去找k
                left=partition+1;
            }else if (partition>k){
                right=partition-1;
            }else {
                return nums[partition];
            }
        }
        return -1;
    }

}
